//
//  main.c
//  LinearListExercise
//
//  Created by Shawn on 2020/4/11.
//  Copyright © 2020 Shawn. All rights reserved.
//


//此工程是关于线性表的一些习题应用

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

//存储空间最大限制
#define MAXSIZE 20

//状态定义
#define SUCCESS 1
#define ERROR 0

#define TRUE 1
#define FALSE 0

//实际数据类型定义
typedef int ItemType;
//返回操作状态
typedef int Status;

//链表结点定义
typedef struct Node{
    int data;
    struct Node *next;
}Node;

typedef struct Node* List;

Status testEmpty(List *a){
    if ((*a) != NULL) {
        printf("非空链表");
    }else{
        printf("空链表");
    }
    return SUCCESS;
}

/// 辅助函数，通过一个数组构建一个链表。
/// @param l 返回的链表，要传入一个空链表进来
/// @param a 数组
/// @param n 数组个数
Status listCreatWithArray(List *l, int *a, int n){
    
    List temp = NULL;
    List r = NULL;
    
    
    for (int i = 0; i < n; i++) {
        if (*l == NULL) {
            *l = (List)malloc(sizeof(Node));
            
            if (!l) {
                return ERROR;
            }
            
            (*l)->data = a[i];
            (*l)->next = NULL;
            r = (*l);
        }else{
            temp = (List)malloc(sizeof(Node));
            temp->data = a[i];
            temp->next = NULL;
            
            r->next = temp;
            r = temp;
        }
    }
    return SUCCESS;
}

/// 遍历循环链表
/// @param l 链表
Status listPrint(List l){
    
    if (!l) {
        return ERROR;
    }else{
        List t;
        t = l;
        printf("链表信息\n");
        do {
            printf("%d, ", t->data);
            t = t->next;
        } while (t); // 若当前节点为头，说明已经打印完毕
        printf("\n");
    }
    return SUCCESS;
}


/// 题目1：将两个递增的链表合为一个链表。要求：结果链表不使用新的空间，而且不含有重复数据。
/// @param a 第一个链表，此处也用它带回结果。
/// @param b 第二个链表。
Status listMerge(List *a, List *b){
    List p, q, k, temp, res, tail;
    //    p，q 两个链表的遍历指针。
    //    k 挑选出适合插入结果链表的结点。
    //    temp 删除结点时的临时指针。
    //    res 结果链表的头，最后会给 a，这里就是为了代码写着方便。
    //    tail 结果指针的尾。
    
    p = (*a);
    q = (*b);
    
    res = NULL;
    tail = NULL;
    
    while (p && q) {
        //        挑选需要操作的结点
        if (q->data < p->data) {
            k = q;
            q = q->next;
        }else if (q->data > p->data) {
            k = p;
            p = p->next;
        }else{
            k = q;
            q = q->next;
            
            temp = p;
            p = p->next;
            free(temp);
            
        }
        
        
        if (!res) {
            res = k;
            tail = k;
        }else{
            tail->next = k;
            tail = k;
        }
        
    }
    
    tail->next = q ? q : p;
    
    *a = res;
    printf("链表合并成功！");
    return SUCCESS;
}

Status listIntersect(List *a, List *b){
    List p, q, k, temp, res, tail;
    //    p,q a,b 的遍历指针。
    //    k 挑选出符合规则的结点。
    //    temp 释放时的临时结点。
    //    res 结果链表的头，最后会赋值给 a，只是为了代码方便。
    //    tail 结果链表的尾。
    
    
    p = *a;
    q = *b;
    
    k = res = temp = tail = NULL;
    
    while (q && p) {
        //        挑选符合规则的元素
        if (q->data == p->data) {
            //            相等时，记住一个释放另一个
            k = q;
            q = q->next;
            
            temp = p;
            p = p->next;
            free(temp);
        }else if (q->data > p->data){
            //            较小的结点不可能再有重复了，释放
            temp = p;
            p = p->next;
            free(temp);
            continue;
        }else if (q->data < p->data){
            temp = q;
            q = q->next;
            free(temp);
            continue;
        }
        
        if (!res) {
            res = k;
            tail = res;
        }else{
            tail->next = k;
            tail = tail->next;
        }
    }
    
    //    末尾处理
    tail->next = NULL;
    
    //    多余的元素需要释放掉
    List last = q ? q : p;
    while (last) {
        temp = last;
        last = last->next;
        free(temp);
    }
    
    *a = res;
    return SUCCESS;
}


/// 题目三：链表逆序成一个新的链表。很明显采用头插法即可。
/// @param a 待处理链表
Status listReverse(List *a){
    List res, p, k;
    //    res 结果链表的头。
    //    p 遍历指针。
    //    k 操作结点指针。
    
    k = res = NULL;
    
    p = *a;
    
    while (p) {
        if (!res) {
            res = p;
            p = p->next;
            //            此处注意，这第一个进来的结点是原链表的头，也是结果链表的尾。
            res->next = NULL;
        }else{
            k = p;
            p = p->next;
            
            k->next = res;
            res = k;
        }
    }
    
    *a = res;
    
    return SUCCESS;
}


/// 第四题：从一个增序链表中剪出 大于等于 mink 小于等于maxk 的剪出一段，返回剩余的结点组成的链表。
/// @param a 待操作链表
/// @param mink 左边界
/// @param maxk 右边界
Status listClip(List *a, int mink, int maxk){
    //    思路：由于链表本身递增，所以，只需要从链表中找出属于需要剪出的片段，然后一并剪出即可。
    List p, minFront, maxFront, head, minHead, temp;
    //    p           遍历指针。
    //    minFront    左边界的前驱结点。
    //    maxFront    右边界的前驱结点。
    //    head        原本的链表添加头结点，以便处理，注意最后需要去掉。
    //    minHead     需要剪出片段的首元结点。
    //    temp        删除时的临时指针。
    
    
    minFront = maxFront = NULL;
    
    //    为原链表添加头结点
    head = (List)malloc(sizeof(Node));
    head->next = *a;
    *a = head;
    
    p = *a;
    
    while (p->next) {
        //        若下一个结点值第一次大于等于左边界，那么当前结点则为 minFront.
        if (p->next->data >= mink && !minFront) {
            minFront = p;
        }
        //        若下一个结点值第一次大于右边界，那么当前结点为 maxFront.
        if (p->next->data > maxk && !maxFront) {
            maxFront = p;
        }
        p = p->next;
    }
    
    //    容错
    if (!minFront || !maxFront) {
        printf("mink 和 maxk 的值有误，未获得正确的边界，请检查您的输入！\n");
        return ERROR;
    }
    
    //    剪出片段
    minHead = minFront->next;
    minFront->next = maxFront->next;
    maxFront->next = NULL;
    
    //    释放片段内结点
    while (minHead) {
        temp = minHead;
        minHead = minHead->next;
        free(temp);
    }
    
    //    去掉并释放头结点
    temp = *a;
    *a = (*a)->next;
    free(temp);
    
    return SUCCESS;
}

Status arrayShow(int *array, int n){
    for (int i = 0; i < n; i++) {
        printf("%2d,", *(array + i));
    }
    printf("\n");
    return SUCCESS;
}


Status arrayReverse(int *array, int startIndex, int endIndex){
    
    int optCount = endIndex - startIndex + 1;
    printf("开始操作 %d 和 %d 之间共 %d 个数据。\n", startIndex, endIndex, optCount);
    for (int i = 0; i < optCount / 2; i++) {
        int index1 = startIndex + i;
        int index2 = (endIndex - i);
        printf("%d 和 %d 位置正在互换数据。\n", index1, index2);
        int temp = *(array+index1);
        *(array+index1) = *(array + index2);
        *(array+index2) = temp;
    }
    
    return SUCCESS;
}


///    ------------------第五题------------------
///题目5：将 n(n>1) 个数存入一维数组 R 中，设计算法使得：将 R 中保存的数据左移 p(0< p <n) 个位置。
///例如：R： 1，2，3，4，5，6，7；p：3  结果为： 4，5，6，7，1，2，3。
///注意：算法的时间复杂度和空间复杂度要尽量低。
/// @param a 待处理的数组
/// @param n 数组的长度
/// @param p 移动步数
Status arrayLeftMove(int *a, int n, int p){
    if (p < 0 || p > n) {
        printf("请确认 n,p 的值输入正确(0< p <n)。");
        return ERROR;
    }
    //    思路：先看👇的示例：
    //    a:1234567 p:3
    //    step1:7654321  [0,n-1]逆序； 0,9
    //    step2:4567321  [0,n-p-1]逆序；0,4
    //    step3:4567123  [n-p,n-1]逆序。5,9  5,6,7,8,9|  5,6
    //    完成。
    //    所以我们需要构建一个辅助函数专门用来做指定坐标内的逆序操作。
    arrayReverse(a, 0, n - 1);
    arrayShow(a, n);
    arrayReverse(a, 0, n - p - 1);
    arrayShow(a, n);
    arrayReverse(a, n - p, n - 1);
    arrayShow(a, n);
    
    
    return SUCCESS;
}


///    ------------------第六题------------------
///题目5：已知一个整数序列 A = (a0, a1, a2, ...an-1) 其中 (0 <= ai <= n), (0 <= i <= n)，若存在 ap1 = ap2 = ... = apm = x，且 m > n/2(0 <= pk <= n, 1 <= k <= n)，则称 x 为 A 的主元素。
///例如：A(0, 5, 5, 3, 5, 7, 5, 5) 中 5 是主元素；A(0, 5, 5, 3, 5, 1, 5, 7) 中无主元素。若 A 中的数据存储在一个一维数组中，试设计算法求出 A 主元素，若没有则返回 -1。
///注意：算法的时间复杂度和空间复杂度要尽量低。
/// @param a 数组
/// @param n 数组个数
int mainElement(int *a, int n){
    //    思路：这个题目出的十分巧妙，题意是要找出 A 中总计出现次数超过一半的元素。那么由此可以简单推断：若A的count为偶数 此元素绝对至少连续出现过一次，1213141511 中的 1，若改为 12131415，那么 1 最多只能达到 n/2，并无法超过；若 A 的 Count 为奇数，那么若前面都没有连续出现过一次的话，最后一位一定是该数据，例如 121314151 中的 1。所以一旦一个数据连续出现了，那么他有极大可能就是我们要找的数据。否则他就不会是主元素，我们把这样的元素叫候选人。
    
    //    11xx1: 解释：看前面 1 出现了2次，但是紧接着被xx抵消掉了权重，所以要抢占主元素的地位，后面他还要继续出现，而且要一直以这样的逻辑下去，所有最后的位置有没有出现 1 显得十分重要，不满足这种抢占关系的元素一定不是主元素。
    
    int key, count;
    key = *(a);
    count = 1;
    //    选取候选人
    for (int i = 1; i < n; i++) {
        if (0 == count) {
            key = *(a+i);
        }
        if (*(a+i) == key) {
            count ++;
        }else{
            count --;
        }
    }
    
    //    查验候选人资格
    for (int i = count = 0; i < n; i++) {
        if (*(a+i) == key) {
            count++;
        }
    }
    
    if (count > n/2) {
        return key;
    }else{
        return -1;
    }
    
}


///    ------------------第七题------------------
///题目4：使用单链表保存 m 个整数，结点的结构为（data，link），且 |data| < n。请设计一个算法筛选出一个新的链表，其中新链表对于绝对值相同的结点只保留第一次出现的结点。
///例如：A {21, -15, 15. -7, 15} => A {21, -15, -7}
///要求：时间复杂度尽量高效。
/// @param l 待处理链表，同时，结果也由它带会。
Status deleteEqualNode(List *l, int n){
    //    开辟空间记录元素是否出现过。
    //    alloca：从栈区开辟空间，作用域结束，程序自动回收。
    int *a = alloca(sizeof(int) * n);
    
    List p, res, tail, temp;
    //    p       遍历指针。
    //    res     结果链表的头，其实就是 l。
    //    tail    结果链表的尾。
    //    temp    删除时临时指针。
    
    p = *l;
    res = tail = NULL;
    
    while (NULL != p) {
        int v = abs(p->data);
        
        
        if (*(a+v) != 1) {
            //            若此绝对值未被标记过，说明这是第一次出现，此结点需要记录。
            if (NULL == res) {
                res = p;
                p = p->next;
                tail = res;
            }else{
                tail->next = p;
                p = p->next;
                tail = tail->next;
            }
            *(a+v) = 1;
        }else{
            //            若此绝对值已经被标记过，那么说明这不是第一次出现了，多余结点需要删除。
            temp = p;
            p = p->next;
            free(temp);
        }
        
    }
    
    return SUCCESS;
}






int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    //    ------------------第一题------------------
    //题目1：将两个递增的链表合为一个链表。
    //要求：结果链表不使用新的空间，而且不含有重复数据。
    //    List l1 = NULL;
    //    int a1[] = {1, 3, 5, 7, 9};
    //
    //    List l2 = NULL;
    //    int a2[] = {2, 4, 5, 6, 8, 10};
    //
    //    listCreatWithArray(&l1, a1, 5);
    //    listCreatWithArray(&l2, a2, 6);
    //
    //    listPrint(l1);
    //    listPrint(l2);
    //
    //    listMerge(&l1, &l2);
    //
    //    listPrint(l1);
    //    ------------------第二题------------------
    //题目2：求两个递增链表的交集。
    //要求：结果链表不使用新的空间。
    //
    //    List l1 = NULL;
    //    testEmpty(&l1);
    //    int a1[] = {1, 3, 4, 5, 7, 8, 9};
    //
    //    List l2 = NULL;
    //    int a2[] = {2, 4, 5, 6, 7, 8, 10};
    //
    //    listCreatWithArray(&l1, a1, 7);
    //    listCreatWithArray(&l2, a2, 7);
    //
    //    listPrint(l1);
    //    listPrint(l2);
    //
    //    listIntersect(&l1, &l2);
    //
    //    listPrint(l1);
    //    ------------------第三题------------------
    //题目3：将链表旋转。就是将链表的顺序逆过来变成一个新的链表
    //要求：空间复杂度为O(1)。
    
    //    List l1 = NULL;
    //    testEmpty(&l1);
    //
    //    int a1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    //
    //    listCreatWithArray(&l1, a1, 10);
    //
    //    listPrint(l1);
    //
    //    listReverse(&l1);
    //
    //    listPrint(l1);
    
    //    ------------------第四题------------------
    //题目4：给定俩个数 mink 、 maxk 和链表 a，删除递增链表中 大于等于 mink 和 小于等于 maxk 的所有结点。
    //注意：链表的元素也可能与 mink 和 maxk 不相同。
    
    //    List l1 = NULL;
    //
    //    int a1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    //
    //    listCreatWithArray(&l1, a1, 10);
    //
    //    listPrint(l1);
    //
    //    listClip(&l1, 11, 22);
    //
    //    listPrint(l1);
    
    //    ------------------第五题------------------
    //题目5：将 n(n>1) 个数存入一维数组 R 中，设计算法使得：将 R 中保存的数据左移 p(0<p<n) 个位置。
    //例如：R： 1，2，3，4，5，6，7；p：3  结果为： 4，5，6，7，1，2，3。
    //注意：算法的时间复杂度和空间复杂度要尽量低。
    
    //    int a1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    //
    //    arrayLeftMove(a1, 10, 4);
    //
    //    arrayShow(a1, 10);
    
    
    //    ------------------第六题------------------
    //题目5：已知一个整数序列 A = (a0, a1, a2, ...an-1) 其中 (0 <= ai <= n), (0 <= i <= n)，若存在 ap1 = ap2 = ... = apm = x，且 m > n/2(0 <= pk <= n, 1 <= k <= n)，则称 x 为 A 的主元素。
    //例如：A(0, 5, 5, 3, 5, 7, 5, 5) 中 5 是主元素；A(0, 5, 5, 3, 5, 1, 5, 7) 中无主元素。若 A 中的数据存储在一个一维数组中，试设计算法求出 A 主元素，若没有则返回 -1。
    //注意：算法的时间复杂度和空间复杂度要尽量低。
    
    //    int a1[] = {0, 5, 5, 3, 5, 7, 5, 5};
    //    int a1[] = {0, 5, 5, 3, 5, 1, 5, 7};
    //
    //    int res = mainElement(a1, 8);
    //
    //    (-1 == res) ? printf("此数组无主元素。\n") : printf("此数组的主要元素是：%d.\n",res);
    
    //    ------------------第七题------------------
    //题目4：使用单链表保存 m 个整数，结点的结构为（data，link），且 |data| < n。请设计一个算法筛选出一个新的链表，其中新链表对于绝对值相同的结点只保留第一次出现的结点。
    //例如：A {21, -15, 15. -7, 15} => A {21, -15, -7}
    //要求：时间复杂度尽量高效。
    
    
    List l1 = NULL;
    
    int a1[] = {21, -15, 15, -7, 15};
    
    listCreatWithArray(&l1, a1, 5);
    
    listPrint(l1);
    
    deleteEqualNode(&l1, 50);
    
    listPrint(l1);
    
    
    return 0;
}
